package leetcode;

import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-28 23:01
 **/
public class LeetCode1601 {



    //二进制枚举
    public int maximumRequests(int n, int[][] requests) {
        int[] delta = new int[n];
        int ans = 0;
        int m = requests.length;
        //二进制枚举
        for (int i = 0; i < (1 << m); ++i) {
            //获取当前数i中位为1的个数
            int cnt = Integer.bitCount(i);
            //如果满足请求的个数 < ans,没必要往下进行,直接跳过
            if (cnt <= ans) {
                continue;
            }

            Arrays.fill(delta, 0);
            for (int j = 0; j < m; j++) {
                //如果当前位为1,更新delta
                if ((i & (1 << j)) != 0) {
                    --delta[requests[j][0]];
                    ++delta[requests[j][1]];
                }
            }

            boolean flag = true;
            //如果delta中有一个数不为0,说明不能满足当前轮的请求
            for (int num : delta) {
                if (num != 0) {
                    flag = false;
                    break;
                }
            }

            //更新ans
            if (flag) {
                ans = cnt;
            }
        }


        return ans;
    }


    //回溯法
    //delta[i]表示i号移入(正数)或移出(负数)的员工个数
    //int[] delta;
    //cnt: 满足了员工请求的数目
    //int cnt;
    //楼的个数
    //int n;
    //ans: 满足了员工请求的最大数目
    //int ans;
    //净变化为0的楼数
    //int zero;

    /*public int maximumRequests(int n, int[][] requests) {
        delta = new int[n];
        this.n = n;
        zero = n;
        dfs(requests, 0);
        return ans;
    }

    void dfs(int[][] requests, int pos) {
        if (pos == requests.length) {
            //如果每栋楼净变化为0,则更新ans
            if (zero == n) {
                //更新ans为ans和cnt中的较大值
                ans = Math.max(ans, cnt);
            }
            return;
        }

        //不满足request[pos]的请求
        dfs(requests, pos + 1);

        //满足request[pos]的请求
        int z = zero;
        //满足请求数+1
        ++cnt;
        //移出楼层编号
        int x = requests[pos][0];
        //移入楼层编号
        int y = requests[pos][1];
        //如果移出前x号楼净变化为0,则要更新zero
        zero -= delta[x] == 0 ? 1 : 0;
        //x号楼移出一人
        --delta[x];
        //如果移出后x号楼净变化为0,则需要更新zero
        zero += delta[x] == 0 ? 1 : 0;
        //如果移入前y号楼净变化为0,更新zero
        zero -= delta[y] == 0 ? 1 : 0;
        //y号楼移入一人
        ++delta[y];
        //如果移入后y号楼净变化为0,更新zero
        zero += delta[y] == 0 ? 1 : 0;
        dfs(requests, pos + 1);
        //回溯状态到原来
        --delta[y];
        ++delta[x];
        --cnt;
        zero = z;
    }*/

}
